/*
    XTU OJ: 1376
    by: fifth_light
*/

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int digits[50];
int all_digits;

void number_convert(int num, int base) {
    all_digits = 0;
    while (num != 0) {
        int digit = num % base;
        digits[all_digits++] = digit;
        num /= base;
        // printf("%d", digit);
    }
    // printf("\nlen: %d\n", all_digits);
}

int judge(void) {
    int cnt = all_digits / 2;
    for (int i = 0; i < cnt; i++) {
        // printf("i: %d, d1: %d, d2: %d\n", i, digits[i], digits[all_digits - i - 1]);
        if(digits[i] != digits[all_digits - i - 1]) {
            return 0;
        }
    }
    return 1;
}

int main(void) {
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        int num;
        scanf("%d", &num);
        for (int base = 2; base <= num; base++) {
            number_convert(num, base);
            if (judge()) {
                printf("%d\n", base);
                goto end;
            }
        }
        printf("%d\n", num == 1 ? 2 :  num + 1);
        end:
        num = 0;
    }
    return 0;
}
